// 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

// 数字过大时超时
var combine = function(n, k) {
    let res = [];
    let used = {};
    let use = {};

    function change(nums) {
        if (nums.length == k) {
            let a = nums.slice().sort((a, b) => { return a - b });
            if (use[a]) { return };
            use[a] = true;
            res.push(a);
            return;
        }
        for (let i = 1; i <= n; i++) {
            if (used[i]) { continue };
            used[i] = true;
            nums.push(i);
            change(nums);
            nums.pop();
            used[i] = false;
        }
    }
    change([]);
    return res;
};

// 剪枝，每次减掉与自己的i之前的重复项
const combine = (n, k) => {
    const res = [];

    const helper = (start, path) => { // start是枚举选择的起点 path是当前构建的路径（组合）
        if (path.length == k) {
            res.push(path.slice()); // 拷贝一份path，推入res
            return; // 结束当前递归
        }
        for (let i = start; i <= n; i++) { // 枚举出所有选择
            path.push(i); // 选择
            helper(i + 1, path); // 向下继续选择
            path.pop(); // 撤销选择
        }
    };

    helper(1, []); // 递归的入口，从数字1开始选
    return res;
}

// 对于每个数只有加入或不加入两种情况，二分一次遍历所有情况，到达长度时返回
const combine = (n, k) => {
    const res = [];
    const helper = (n, k, path) => {
        if (n < k || k == 0) { // k比n大了，或，找齐了k个，结束递归
            if (k == 0) { // 找齐k个时，加入解集
                res.push(path.slice());
            }
            return;
        }
        helper(n - 1, k - 1, path.concat(n)); // 选n，C(n-1, k-1)
        helper(n - 1, k, path); // 不选n，C(n-1,k)
    };

    helper(n, k, []);
    return res;
};